package com.asia.algorithmcode.binaryTree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @DESCRIPTION: 二叉树、迭代、递归，调用栈
 * @USER: wanfu
 * @DATE: 2025/4/24 星期四 10:13
 */
public class InorderTraversal {


    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);

        n1.right = n2;
        n2.left = n3;

        List<Integer> integers = new InorderTraversal().inorderTraversal(n1);
        System.out.println(integers);

    }

    List<Integer> resList = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        return iterator(root);
//        return resList;
    }


    /**
     * 二叉树的中序遍历，迭代遍历的写法
     */
    private List<Integer> iterator(TreeNode root) {
        List<Integer> resList = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();

        while (root != null || !deque.isEmpty()) {
            while (root != null) {
                deque.push(root);
                root = root.left;
            }
            TreeNode last = deque.pop();
            resList.add(last.val);
            root = last.right;
        }

        return resList;
    }


    /**
     * 二叉树的中序遍历，递归的写法
     *
     * @param root
     */
    private void recursive(TreeNode root) {
        if (root == null) {
            return;
        }
        recursive(root.left);
        resList.add(root.val);
        recursive(root.right);
    }

}
